/**
 * describe:
 *
 * @author chaP
 * @date 2019/04/07
 */
package CodingTest.AC20190407;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**leetcode-279
 * 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

 示例 1:

 输入: n = 12
 输出: 3
 解释: 12 = 4 + 4 + 4.
 示例 2:

 输入: n = 13
 输出: 2
 解释: 13 = 4 + 9.
 */
public class numSquares {
    //动态规划：
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        for(int i=1;i*i<=n;i++){
            dp[i*i] = 1;
        }
        for(int i = 1;i<=n;i++){
            for(int j = 1;i+j*j<=n;j++){
                dp[i+j*j] = Math.min(dp[i*i]+1,dp[i+j*j]);
            }
        }
        return dp[n];

    }
    //bfs

    public int numSquares1(int n){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        int step = 1;
        boolean[] visited = new boolean[n+1];
        visited[0]=true;
        while(!queue.isEmpty()){
            for(int i = queue.size();i>0;i--){
                int cur = queue.remove();
                for(int j =1;;j++){
                    int next = cur +j*j;
                    if(next>n){
                        break;
                    }else if(next == n){
                        return step;
                    }
                    if(!visited[next]){
                        queue.add(next);
                        visited[next] = true;
                    }
                }
            }
            step++;
        }return 0;
    }



    public static void main(String[] args) {
        numSquares ns = new numSquares();
        System.out.println(ns.numSquares1(13));
    }
}
